package seiacpjava_a2.datastructures.tree;

import seiacpjava_a2.datastructures.DataStructure;

public class BinarySearchTreeRecursive extends DataStructure {
	
	private TreeNode rootNode;
	private int size;
	private int nbrAccess;
	
	public BinarySearchTreeRecursive() {
	}
	
	public void add(int... items) {
		for(int item: items) {
			add(item);
		}
	}

	@Override
	public void add(int item) {
		if(this.rootNode == null) {
			this.rootNode = new TreeNode(item, null, null);
			size++;
		} else insert(this.rootNode,item);
	}
	
	private void insert(TreeNode node, int item) {
		if(item == node.getItem()) 
			return;
		else if (item < node.getItem()) {
			if ( node.getLeft() == null) {
				node.setLeft(new TreeNode(item,null,null));
				size++;
			} else {
				insert(node.getLeft(),item);
			}
		} else {
			if ( node.getRight() == null) {
				node.setRight(new TreeNode(item, null, null));
				size++;
			} else {
				insert(node.getRight(),item);
			}
		}
	}

	@Override
	public boolean contains(int item) {
		this.nbrAccess = 0;
		boolean isFound = false;
		SearchResult result = null;
		
		if (this.rootNode == null)
			this.numberOfAccesses = this.nbrAccess;
			//result = new SearchResult(this.nbrAccess, isFound);
		else {
			result = search(item,this.rootNode);
			isFound = result.isFound();
			this.numberOfAccesses = result.getNbrAccess();
		}
		return isFound;
		
	}
	
	public SearchResult search(int item, TreeNode node) {
		if(node == null) {
			this.nbrAccess++;
			return new SearchResult(this.nbrAccess, false);
		}
			
			
		if ( item < node.getItem()) {
			this.nbrAccess++;
			return search(item,node.getLeft());
		} else if ( item > node.getItem()) {
			this.nbrAccess++;
			return search(item,node.getRight());
		} else {
			this.nbrAccess++;
			return new SearchResult(this.nbrAccess, true);
		}
	}
	
	public int getSize() {
		return this.size;
	}

	@Override
	public String getDatatStructureName() {
		return "Binary Search Tree";
	}

}